Robust Distributed Routing in Dynamical Flow Networks - Part II: Strong Resilience, Equilibrium Selection and Cascaded Failures

摘要

Strong resilience properties of dynamical flow networks are analyzed fordistributed routing policies. The latter are characterized by the property thatthe way the inflow at a non-destination node gets split among its outgoinglinks is allowed to depend only on local information about the current particledensities on the outgoing links. The strong resilience of the network isdefined as the infimum sum of link-wise flow capacity reductions under whichthe network cannot maintain the asymptotic total inflow to the destination nodeto be equal to the inflow at the origin. A class of distributed routingpolicies that are locally responsive to local information is shown to yield themaximum possible strong resilience under such local information constraints foran acyclic dynamical flow network with a single origin-destination pair. Themaximal strong resilience achievable is shown to be equal to the minimum noderesidual capacity of the network. The latter depends on the limit flow of theunperturbed network and is defined as the minimum, among all thenon-destination nodes, of the sum, over all the links outgoing from the node,of the differences between the maximum flow capacity and the limit flow of theunperturbed network. We propose a simple convex optimization problem to solvefor equilibrium limit flows of the unperturbed network that minimize averagedelay subject to strong resilience guarantees, and discuss the use of tolls toinduce such an equilibrium limit flow in transportation networks. Finally, wepresent illustrative simulations to discuss the connection between cascadedfailures and the resilience properties of the network.